package com.lijing.HeapSort;

import com.lijing.StopWatch.StopWatch;

/**
 * @Description 堆排序
 * @title: HeapSort
 * @Author LiJing
 * @Date: 2021/2/229:56 下午
 * @Version 1.0
 */
public class Heap {
    public static void main(String[] args) {
        int n = 8000000;
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int)(Math.random()*n*10);
            //System.out.println(arr[i]);
        }
        StopWatch sw = new StopWatch();
        Heap.sort(arr);
        double time = sw.elapsedTime();
        //System.out.println(Arrays.toString(arr));
        System.out.println("Cost time:"+time+"s");
    }

    public static void sort(Comparable[] arr){
        for (int i = arr.length/2-1; i >= 0; i--) {
            adjustHeap(arr,i, arr.length);
        }
        for (int j = arr.length-1; j > 0; j--) {
            exch(arr,0,j);
            adjustHeap(arr,0,j);
        }
    }


    /**
     * 将以i为父节点的树调整为一个大顶堆
     * @param arr 待调整的数组
     * @param i 表示非叶子结点在数组中的索引
     * @param length 表示需要调整的元素个数
     */
    public static void adjustHeap(Comparable[] arr, int i, int length){
        Comparable temp = arr[i];
        /*
        i节点下的子树
         */
        for (int j = 2*i+1; j < length; j = 2*j+1) {
            if (j+1 < length && less(arr[j],arr[j+1])){
                j++;
            }
            if (less(temp,arr[j])){
                arr[i] = arr[j];
                i = j;
            }else {
                break;
            }
        }
        arr[i] = temp;

    }

    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] arr, int i, int j){
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
